home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / usenet / sources / volume90 / util / bsindex1 / part01 / src / expression.c < prev    next >
C/C++ Source or Header  |  1990-02-02  |  11KB  |  520 lines
  1. /*
  2.  * EXPRESSION.C
  3.  *
  4.  * This module contains the routines needed to parse and evaluate an
  5.  * expression. This is used while selecting which files to print.
  6.  *
  7.  *    This is the BNF for the set of expressions recognised by the
  8.  *    database searcher. It doesn't contain any semantic information however.
  9.  *
  10.  *    Expression            ::= Boolean | Boolean Operator Expression | ALL
  11.  *    Operator            ::= AND | OR 
  12.  *    Boolean                ::= NOT Boolean                |
  13.  *                            '(' Expression ')'        |
  14.  *                            BoolIdent                |
  15.  *                            NumIdent    Op Value    |
  16.  *                            StringIdent Op String    |
  17.  *                            DateIdent    Op Date
  18.  *    Op                    ::= '<' | '>' | '<=' | '>=' | '=' | '<>'
  19.  *    BoolIdent            ::= BINARY | ONLINE | LOCAL | VALID
  20.  *    StringIdent            ::= COMMENT | DISKNAME | NAME | OWNER | PATHNAME
  21.  *    NumIdent            ::= ACCESS | SECTION | DIRECTORY | DISKDIRNUM |
  22.  *                            SIZE | KSIZE
  23.  *    DateIdent            ::= DATE
  24.  *    String                ::= (Text enclosed in quotes)
  25.  *    Value                ::= (A number)
  26.  *    Date                ::= (A date in the format "dd-mon-yy")
  27.  *
  28.  */
  29.  
  30. #ifndef LATTICE_50
  31. #include "system.h"
  32. #endif
  33.  
  34. #include "bbsindex.h"
  35.  
  36. #define mystrcmp stricmp        /* Make match() insensitive to case */
  37.  
  38. /*
  39.  *        BNF procedures
  40.  */
  41.  
  42. void bnf_op(), bnf_date(), bnf_expression(), bnf_boolean();
  43.  
  44. /*
  45.  *        Global variable(s)
  46.  */
  47.  
  48. static int treepos;                /* Next free entry in tree array    */
  49. static int curtoken;            /* Current token                    */
  50. static int curvalue;            /* Current number with E_NUMBER        */
  51. static char curstring[MAXCOM];    /* Current string with E_STRING        */
  52.  
  53. /*
  54.  *        Tokens recognised as special in expressions
  55.  */
  56.  
  57. struct {
  58.     int tag;
  59.     char *name;
  60. } tokens[] = {
  61.     
  62.     {    E_EQ,            "="            },
  63.     {    E_NE,            "<>"        },
  64.     {    E_LE,            "<="        },
  65.     {    E_GE,            ">="        },
  66.     {    E_LT,            "<"            },
  67.     {    E_GT,            ">"            },
  68.     {    E_AND,            "AND"        },
  69.     {    E_OR,            "OR"        },
  70.     {    E_NOT,            "NOT"        },
  71.     {    E_ALL,            "ALL"        },
  72.     {    E_OPENPAR,        "("            },
  73.     {    E_CLOSEPAR,        ")"            },
  74.     {    E_TEXT,            "TEXT"        },
  75.     {    E_REMOTE,        "REMOTE"    },
  76.     {    E_INVALID,        "INVALID"    },
  77.     {    E_OFFLINE,        "OFFLINE"    },
  78.     {    NULL,            NULL        }
  79. };
  80.  
  81. /*
  82.  *        wild()
  83.  *        ------
  84.  *        This routine does a wildcard match on the two specified strings.
  85.  *        The first string contains the string to check, and the second string
  86.  *        containts the wildcard pattern to check against. The special wild
  87.  *        card characters are '?' which matches any single characters, and
  88.  *        '*' which matches any number of characters. 0 is returned if the
  89.  *        the two strings match, else a +ve or -ve number.
  90.  *
  91.  */
  92. int wild(s,w)
  93. char *s;
  94. char *w;
  95. {
  96.     char *p;
  97.     char ch;
  98.  
  99.     while (*w && *s) {
  100.         switch (*w) {
  101.  
  102.             case '*':
  103.                 ch = toupper(w[1]);
  104.                 if (!ch)
  105.                     return (0);
  106.                 for (p = s; *p; p++) {
  107.                     if (toupper(*p) == ch || ch == '?') {
  108.                         if (!wild(p,w+1))
  109.                             return (0);
  110.                     }
  111.                 }
  112.                 return (toupper(*p)-ch);
  113.  
  114.             case '?':
  115.                 break;
  116.  
  117.             default:
  118.                 if (toupper(*s) != toupper(*w))
  119.                     return (toupper(*s)-toupper(*w));
  120.         }
  121.         w++;
  122.         s++;
  123.     }
  124.     return (toupper(*s)-toupper(*w));
  125. }
  126.  
  127.  
  128. /*
  129.  *        Dirty great macro to compare two values according to an operator
  130.  */
  131. #define e_cmp(v1,op,v2)                        \
  132.     switch (op) {                            \
  133.         case E_EQ: return ((v1) == (v2));    \
  134.         case E_NE: return ((v1) != (v2));    \
  135.         case E_LT: return ((v1) <  (v2));    \
  136.         case E_GT: return ((v1) >  (v2));    \
  137.         case E_LE: return ((v1) <= (v2));    \
  138.         case E_GE: return ((v1) >= (v2));    \
  139.     }
  140.  
  141. #define e_numcmp(n)        e_cmp(n, e->op, e->num)
  142. #define e_strcmp(s)        e_cmp(mystrcmp(s,e->text), e->op, 0)
  143. #define e_wildcmp(s)    e_cmp(wild(s,e->text), e->op, 0)
  144.  
  145. /*
  146.  *        match()
  147.  *        -------
  148.  *        Scans the the parse tree, and returns TRUE if the current
  149.  *        record matches the criteria in the tree, else FALSE.
  150.  *
  151.  *        Aside: Aren't C macros wonderful? Just think how long this function
  152.  *        would be if it wasn't for the above e_cmp, e_numcmp and e_strcmp
  153.  *        macros.
  154.  */
  155. int match(p, e)
  156. UDHEAD *p;
  157. EXPR *e;
  158. {
  159.     switch (e->field) {
  160.         
  161.         case E_AND:            return (match(p, e->left) && match(p, e->right));
  162.         case E_OR:            return (match(p, e->left) || match(p, e->right));
  163.         case E_NOT:            return (!match(p, e->left));
  164.         case E_ALL:            return (TRUE);
  165.         case I_LOCAL:        return ((int)p->local);
  166.         case I_BINARY:        return ((int)p->bin);
  167.         case I_VALID:        return ((int)p->valid);
  168.         case I_ONLINE:        return ((int)p->online);
  169.         case E_REMOTE:        return (!(int)p->local);
  170.         case E_TEXT:        return (!(int)p->bin);
  171.         case E_INVALID:        return (!(int)p->valid);
  172.         case E_OFFLINE:        return (!(int)p->online);
  173.         case I_ACCESS:        e_numcmp(p->accesses);
  174.         case I_DATE:        e_numcmp(p->date);
  175.         case I_DIRECTORY:    e_numcmp(p->dir);
  176.         case I_DISKDIRNUM:    e_numcmp(p->dirnum);
  177.         case I_KSIZE:        e_numcmp(BTOK(p->length));
  178.         case I_SECTION:        e_numcmp(p->section);
  179.         case I_SIZE:        e_numcmp(p->length);
  180.         case I_DISKNAME:    e_strcmp(p->disk_name);
  181.         case I_COMMENT:        e_strcmp(p->desc);
  182.         case I_NAME:        e_strcmp(p->cat_name);
  183.         case I_OWNER:        e_strcmp(p->owner);
  184.         case W_DISKNAME:    e_wildcmp(p->disk_name);
  185.         case W_COMMENT:        e_wildcmp(p->desc);
  186.         case W_NAME:        e_wildcmp(p->cat_name);
  187.         case W_OWNER:        e_wildcmp(p->owner);
  188.     }
  189. }
  190.  
  191. /*
  192.  *        newnode()
  193.  *        ---------
  194.  *        This function allocates a new node from the tree array, and returns
  195.  *        a pointer to it. If overflow occurs, it aborts with an error message.
  196.  */
  197.  
  198. EXPR *newnode()
  199. {
  200.     treepos++;
  201.     if (treepos >= MAXEXPR) {
  202.         scripterror("expression to complex\n");
  203.         Cleanup(10);
  204.     }
  205.     return (&tree[treepos]);
  206. }
  207.  
  208. /*
  209.  *        readtoken()
  210.  *        -----------
  211.  *        This function reads the next token from the command line, starting
  212.  *        at position curpos. curtoken is set to the type of token received.
  213.  *        If it was E_STRING, then curstring points to the string it
  214.  *        represents (without the quotes). If it was E_NUM, then curvalue
  215.  *        points to the number represented. If the end of the line is
  216.  *        reached, E_END is automatically set.
  217.  */
  218.  
  219. #define nextch()        (ch = combuf[compos++])
  220. #define ungetnext()        (compos--)
  221.  
  222. void readtoken()
  223. {
  224.     char *p = curstring, ch;
  225.     int i;
  226.  
  227.     if (compos >= comlen) {
  228.         curtoken = E_END;
  229.         return;
  230.     }
  231.  
  232.     do {
  233.         nextch();
  234.     } while (ch == CHAR_SPACE);
  235.  
  236.     if (ch == CHAR_QUOTES) {            /* Handle string in quotes */
  237.         curtoken = E_STRING;
  238.         nextch();
  239.         if (*p == CHAR_NULL) {
  240.             curtoken = E_END;
  241.             return;
  242.         }
  243.         do {
  244.             *p++ = ch;
  245.             nextch();
  246.         } while (ch && ch != CHAR_QUOTES);
  247.         *p = CHAR_NULL;
  248.         return;
  249.     }
  250.  
  251.     if (isdigit(ch)) {                /* Numeric value? */
  252.         curtoken = E_NUMBER;
  253.         curvalue = 0;
  254.         do {
  255.             curvalue = curvalue * 10 + (ch - '0');
  256.             nextch();
  257.         } while (isdigit(ch));
  258.         ungetnext();
  259.         return;
  260.     }
  261.  
  262.     if (isalpha(ch)) {                /* Alphabetic identifier? */
  263.         do {
  264.             *p++ = ch;
  265.             nextch();
  266.         } while (isalpha(ch));
  267.     } else if (ch == CHAR_NULL) {    /* At end of line? */
  268.         curtoken = E_END;
  269.         return;
  270.     } else {                        /* Must be punctuation */
  271.         do {
  272.             *p++ = ch;
  273.             nextch();
  274.         } while (ch && !isalpha(ch) && !isdigit(ch) && ch != CHAR_SPACE
  275.                                     && ch != CHAR_QUOTES);
  276.     }
  277.     *p = CHAR_NULL;
  278.     ungetnext();
  279.  
  280.     /* Check for character A - F */
  281.     if (curstring[1] == CHAR_NULL) {
  282.         switch (curstring[0]) {
  283.             case 'A': case 'B': case 'C':
  284.             case 'D': case 'E': case 'F':
  285.                 curvalue = curstring[0] + 10 - 'A';
  286.                 curtoken = E_NUMBER;
  287.                 return;
  288.         }
  289.     }
  290.  
  291.     /* Now find token that matches string */
  292.     for (i = 0; i < MAXINDEX; i++) {
  293.         if (!strcmp(curstring, indexes[i].name)) {
  294.             curtoken = indexes[i].tag;
  295.             return;
  296.         }
  297.     }
  298.     for (i = 0; tokens[i].name; i++) {
  299.         if (!strcmp(curstring, tokens[i].name)) {
  300.             curtoken = tokens[i].tag;
  301.             return;
  302.         }
  303.     }
  304.     scripterror("unrecognised symbol '");
  305.     print2(curstring,"' in expression\n");
  306.     Cleanup(10);
  307. }
  308.  
  309.  
  310. /*
  311.  *        com_select()
  312.  *        ------------
  313.  *        This command parses the expression in the command buffer starting
  314.  *        at position compos, and builds an expression tree representing it.
  315.  *        This tree is stored in tree[], starting at element 0. This expression
  316.  *        tree is used when match() is called.
  317.  */
  318.  
  319. void com_select()
  320. {
  321.     treepos = 0;
  322.     readtoken();
  323.     bnf_expression(tree);
  324. }
  325.  
  326. /*
  327.  *        bnf_expression()
  328.  *        ----------------
  329.  *        Parses the BNF line:
  330.  *
  331.  *        Expression ::= Boolean | Boolean Operator Expression | ALL
  332.  *
  333.  */
  334. void bnf_expression(e)
  335. EXPR *e;
  336. {
  337.     EXPR dummy;
  338.  
  339.     if (curtoken == E_ALL)
  340.         e->field = E_ALL;
  341.     else {
  342.         bnf_boolean(&dummy);
  343.         if (curtoken == E_AND || curtoken == E_OR) {
  344.             e->field   = curtoken;
  345.             e->left    = newnode();
  346.             e->right   = newnode();
  347.             *(e->left) = dummy;
  348.             readtoken();
  349.             bnf_expression(e->right);
  350.         } else
  351.             *e = dummy;
  352.     }
  353. }
  354.  
  355. /*
  356.  *        bnf_boolean()
  357.  *        -------------
  358.  *        Parses the following BNF line:
  359.  *
  360.  *        Boolean    ::= NOT Boolean                |
  361.  *                    '(' Expression ')'        |
  362.  *                    BoolIdent                |
  363.  *                    NumIdent    Op Value    |
  364.  *                    StringIdent Op String    |
  365.  *                    DateIdent    Op Date
  366.  */
  367. void bnf_boolean(e)
  368. EXPR *e;
  369. {
  370.     char *p;
  371.  
  372.     e->field = curtoken;
  373.     switch (curtoken) {
  374.  
  375.         case E_NOT:
  376.             e->left = newnode();
  377.             readtoken();
  378.             bnf_boolean(e->left);
  379.             break;
  380.  
  381.         case E_OPENPAR:
  382.             readtoken();
  383.             bnf_expression(e);
  384.             if (curtoken != E_CLOSEPAR) {
  385.                 scripterror("missing close parenthesis\n");
  386.                 Cleanup(10);
  387.             }
  388.             readtoken();
  389.             break;
  390.  
  391.         case I_BINARY:
  392.         case I_VALID:
  393.         case I_ONLINE:
  394.         case I_LOCAL:
  395.         case E_TEXT:
  396.         case E_INVALID:
  397.         case E_OFFLINE:
  398.         case E_REMOTE:
  399.             readtoken();
  400.             break;
  401.  
  402.         case I_ACCESS:
  403.         case I_SECTION:
  404.         case I_DIRECTORY:
  405.         case I_DISKDIRNUM:
  406.         case I_SIZE:
  407.         case I_KSIZE:
  408.             readtoken();
  409.             bnf_op(e);
  410.             if (curtoken != E_NUMBER) {
  411.                 scripterror("number expected in expression\n");
  412.                 Cleanup(10);
  413.             }
  414.             e->num = curvalue;
  415.             readtoken();
  416.             break;
  417.  
  418.         case I_COMMENT:
  419.         case I_DISKNAME:
  420.         case I_NAME:
  421.         case I_OWNER:
  422.         case I_PATHNAME:
  423.             readtoken();
  424.             bnf_op(e);
  425.             if (curtoken != E_STRING) {
  426.                 scripterror("string expected in expression\n");
  427.                 Cleanup(10);
  428.             }
  429.             e->text = mymalloc(strlen(curstring)+1);
  430.             strcpy(e->text, curstring);
  431.             /*
  432.              *        Now check the string, and see if it contains any wildcard
  433.              *         characters. If it does, use operation W_{string}
  434.              *        instead of E_{string}. If it doesn't, use the standard
  435.              *        strcmp which is much faster.
  436.              */
  437.             for (p = curstring; *p; *p++) {
  438.                 if (*p == '*' || *p == '?') {
  439.                     e->field = tokentowild(e->field);
  440.                     break;
  441.                 }
  442.             }
  443.             readtoken();
  444.             break;
  445.  
  446.         case I_DATE:
  447.             readtoken();
  448.             bnf_op(e);
  449.             bnf_date(e);
  450.             break;
  451.  
  452.         default:
  453.             scripterror("error in expression\n");
  454.             Cleanup(10);
  455.     }
  456. }
  457.  
  458. /*
  459.  *        bnf_op
  460.  *        ------
  461.  *        Sets the operation field of the specified expression to the value
  462.  *        of the next token on the command line.
  463.  */
  464. void bnf_op(e)
  465. EXPR *e;
  466. {
  467.     switch (curtoken) {
  468.         case E_EQ:
  469.         case E_NE:
  470.         case E_LT:
  471.         case E_GT:
  472.         case E_LE:
  473.         case E_GE:
  474.             e->op = curtoken;
  475.             readtoken();
  476.             break;
  477.  
  478.         default:
  479.             scripterror("expected comparison operator\n");
  480.             Cleanup(10);
  481.     }
  482. }
  483.  
  484. /*
  485.  *        bnf_date()
  486.  *        -----------
  487.  *        Reads a date from the command line, validates it, and sets the
  488.  *        'num' field in the expression to its numerical value. The date
  489.  *        is in the format "dd-mon-yy", e.g. "15-Jun-89"
  490.  */
  491. void bnf_date(e)
  492. EXPR *e;
  493. {
  494.     int day, month, year;
  495.  
  496.     if (curtoken != E_STRING) {
  497.         scripterror("expected date string in expression\n");
  498.         Cleanup(10);
  499.     }
  500.  
  501.     if (strlen(curstring) != 9 ||
  502.             curstring[2] != '-' || curstring[6] != '-') {
  503.         scripterror("Invalid date format (should be dd-mon-yy)\n");
  504.         Cleanup(10);
  505.     }
  506.  
  507.     day = atoi(curstring);
  508.     year = atoi(curstring+7);
  509.     for (month = 0; month < 12 && strnicmp(curstring+3, months[month], 3);
  510.                                                         month++)
  511.         ;
  512.     if ((day < 1 || day > 31) || (month < 1 || month > 12) ||
  513.                 (year < 1 || year > 99)) {
  514.         scripterror("Invalid date format (should be dd-mon-yy)\n");
  515.         Cleanup(10);
  516.     }
  517.     e->num = (((year * 13) + month) << 5) + day;
  518.     readtoken();
  519. }
  520.